package 动态规划;

public class 最长回文子串5 {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ans =null;
        ans = s.substring(0, 1); // 初始化答案为第一个字符
        boolean[][]dp = new boolean[n][n];
        //自己和自己肯定是回文
        for(int i=0;i<n;i++){
            dp[i][i]= true;
        }
        int maxLen =1;
        for(int i=2;i<=n;i++){
            for(int l=0;l<n;l++){
                int r = l+i-1;
                if(r>=n)break;
                if(s.charAt(l)!=s.charAt(r)){
                    dp[l][r]=false;
                }else
                if(r-l<3){
                    dp[l][r]=true;
                }else{
                    dp[l][r]=dp[l+1][r-1];
                }
                if(dp[l][r]&&r-l+1>maxLen){
                    maxLen=r-l+1;
                    ans=s.substring(l,r+1);
                }
            }

        }
        return ans;

    }
    }
